home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / c / bplus11.zip / BPLUS.C next >
C/C++ Source or Header  |  1988-12-08  |  26KB  |  998 lines
  1. /********************************************************************/
  2. /*                                                                  */
  3. /*             BPLUS file indexing program - Version 1.1            */
  4. /*                                                                  */
  5. /*                      A "shareware program"                       */
  6. /*                                                                  */
  7. /*                                                                  */
  8. /*                      Copyright (C) 1987 by                       */
  9. /*                                                                  */
  10. /*                      Hunter and Associates                       */
  11. /*                      7050 NW Zinfandel Lane                      */
  12. /*                      Corvallis, Oregon  97330                    */
  13. /*                      (503) 745 - 7186                            */
  14. /*                                                                  */
  15. /********************************************************************/
  16.  
  17.  
  18. #include <stdio.h>
  19. #include <fcntl.h>
  20. #ifdef    MSC
  21. #include <io.h>
  22. #endif
  23. #include <sys/types.h>            /*  delete this line for Turbo C  */
  24. #include <sys/stat.h>
  25. #include <string.h>
  26. #include "bplus.h"
  27.  
  28.  
  29. /*  macros, constants, data types  */
  30.  
  31. #define  NULLREC      (-1L)
  32. #define  FREE_BLOCK   (-2)
  33.  
  34. #define  ENT_ADR(pb,off)  ((ENTRY*)((char*)((pb)->entries) + off))
  35. #define  ENT_SIZE(pe)     strlen((pe)->key) + 1 + 2 * sizeof(RECPOS)
  36. #define  BUFDIRTY(j)      (mci->cache[j].dirty)
  37. #define  BUFHANDLE(j)     (mci->cache[j].handle)
  38. #define  BUFBLOCK(j)      (mci->cache[j].mb)
  39. #define  BUFCOUNT(j)      (mci->cache[j].count)
  40. #define  CB(j)            (pci->pos[j].cblock)
  41. #define  CO(j)            (pci->pos[j].coffset)
  42.  
  43.  
  44.                     /*    ATTENTION MICROSOFT USERS   */
  45.                     /* Microsoft changed the memcpy   */
  46.                     /* library routine in the C 5.0   */
  47.                     /* compiler.  The following macro */
  48.                     /* must be used for Microsoft 5.0 */
  49.                     /* and the Quick C compiler.      */
  50.  
  51. #if    1
  52. #define memcpy            memmove
  53. #endif    /* if not needed */
  54.  
  55. /*  declare some global variables  */
  56.  
  57. IX_DESC      *pci;
  58. IX_BUFFER    bt_buffer;
  59. IX_BUFFER    *mci = &bt_buffer;
  60. BLOCK        *block_ptr;
  61. BLOCK        *spare_block;
  62. int          cache_ptr = 0;
  63. int          cache_init = 0;
  64. int          split_size = IXB_SPACE;
  65. int          comb_size  = (IXB_SPACE/2);
  66.  
  67. /* ================ internal procedures ================ */
  68. static void pascal error Param((int, long));
  69. static void pascal read_if Param((RECPOS, char *, int));
  70. static void pascal write_if Param((int, RECPOS, char *, int));
  71. static int  pascal creat_if Param((char *));
  72. static int  pascal open_if Param((char *));
  73. static void pascal close_if Param((int));
  74. static void pascal update_block Param((void));
  75. static void pascal init_cache Param((void));
  76. static int  pascal find_cache Param((RECPOS));
  77. static int  pascal new_cache Param((void));
  78. static void pascal load_cache Param((RECPOS));
  79. static void pascal get_cache Param((RECPOS));
  80. static void pascal retrieve_block Param((int, RECPOS));
  81. static int  pascal prev_entry Param((int));
  82. static int  pascal next_entry Param((int));
  83. static void pascal copy_entry Param((ENTRY *, ENTRY *));
  84. static int  pascal scan_blk Param((int));
  85. static int  pascal last_entry Param((void));
  86. static void pascal write_free Param(( RECPOS, BLOCK *));
  87. static RECPOS pascal get_free Param((void));
  88. static int  pascal find_block Param((ENTRY *, int *));
  89. static void pascal movedown Param((BLOCK *, int, int));
  90. static void pascal moveup Param((BLOCK *, int, int));
  91. static void pascal ins_block Param((BLOCK *, ENTRY *, int));
  92. static void pascal del_block Param((BLOCK *, int));
  93. static void pascal split Param((int, ENTRY *, ENTRY *));
  94. static void pascal ins_level Param((int, ENTRY *));
  95. static int  pascal insert_ix Param((ENTRY *, IX_DESC *));
  96. static int  pascal find_ix Param((ENTRY *, IX_DESC *, int));
  97. static int  pascal combineblk Param((RECPOS, int));
  98. static void pascal replace_entry Param((ENTRY *));
  99. static void print_blk Param((BLOCK *));
  100.  
  101.  
  102. /*  file I/O for B-PLUS module  */
  103.  
  104. static void pascal 
  105. error(j, l)
  106.   int j;
  107.   long l;
  108.   {
  109.     static char *msg[3] = {"ERROR - CANNOT OPEN/CLOSE FILE",
  110.                            "ERROR WHILE READING FILE",
  111.                            "ERROR WHILE WRITING FILE"};
  112.     (void) printf("\n  %s - Record Number %ld\n", msg[j], l);
  113.     exit(1);
  114.   } /* error */
  115.  
  116.  
  117. static void pascal 
  118. read_if(start, buf, nwrt)
  119.   RECPOS start;
  120.   char *buf;
  121.   int nwrt;
  122.   {
  123.     long err;
  124.     err = start - lseek(pci->ixfile, start, SEEK_SET);
  125.     if (err == 0) err = nwrt - read(pci->ixfile, buf, nwrt);
  126.     if (err != 0) error(1, start);
  127.   } /* read_if */
  128.  
  129.  
  130. static void pascal 
  131. write_if(handle, start, buf, nwrt)
  132.   int handle;
  133.   RECPOS start;
  134.   char *buf;
  135.   int nwrt;
  136.   {
  137.     long err;
  138.     err = start - lseek(handle, start, SEEK_SET);
  139.     if (err == 0) err = nwrt - write(handle, buf, nwrt);
  140.     if (err != 0) error(2, start);
  141.   } /* write_if */
  142.  
  143.  
  144. static int pascal 
  145. creat_if(fn)
  146.   char *fn;
  147.   {
  148.     int   ret;
  149.     ret = open(fn,O_RDWR|O_CREAT|O_TRUNC|O_BINARY,S_IREAD|S_IWRITE);
  150.     if (ret  < 0) error(0,0L);
  151.     return (ret);
  152.   } /* creat_if */
  153.  
  154.  
  155. static int pascal 
  156. open_if(fn)
  157.   char *fn;
  158.   {
  159.     int  ret;
  160.     ret = open(fn,O_RDWR|O_BINARY);
  161.     if (ret < 1) error(0,0L);
  162.     return (ret);
  163.   } /* open_if */
  164.  
  165.  
  166. static void pascal 
  167. close_if(handle)
  168.   int handle;
  169.   {
  170.     if(close(handle) < 0)  error(2,0L);
  171.   } /*  close_if */
  172.  
  173.  
  174. int cdecl 
  175. open_index(name, pix, dup)
  176.   char *name;
  177.   IX_DESC *pix;
  178.   int dup;
  179.   {
  180.     pci = pix;
  181.     pci->ixfile = open_if(name);
  182.     pci->duplicate = dup;
  183.     read_if(0L,(char *)&(pix->root), (sizeof(BLOCK) + sizeof(IX_DISK)));
  184.     if (!cache_init)
  185.       {
  186.         init_cache();
  187.         cache_init = 1;
  188.       }
  189.     first_key(pix);
  190.     return ( IX_OK );
  191.   } /* open_index */
  192.  
  193.  
  194. int cdecl 
  195. close_index(pix)
  196.   IX_DESC *pix;
  197.   {
  198.     int i;
  199.     write_if(pix->ixfile, 0L,(char *)&(pix->root),
  200.                (sizeof(BLOCK) + sizeof(IX_DISK)));
  201.     for (i = 0; i < NUM_BUFS; i++)
  202.       if (BUFHANDLE(i) == pix->ixfile)
  203.         {
  204.           if (BUFDIRTY(i))
  205.             {
  206.               write_if(BUFHANDLE(i),
  207.                        BUFBLOCK(i).brec,
  208.                        (char *) &BUFBLOCK(i),
  209.                        (int) sizeof(BLOCK));
  210.               BUFDIRTY(i) = 0;
  211.             }
  212.           BUFBLOCK(i).brec = NULLREC;
  213.       }
  214.     close_if(pix->ixfile);
  215.     return( IX_OK );
  216.   } /* close_index */
  217.  
  218.  
  219. int cdecl 
  220. make_index(name, pix, dup)
  221.   char *name;
  222.   IX_DESC *pix;
  223.   int dup;
  224.   {
  225.     pci = pix;
  226.     pci->ixfile = creat_if(name);
  227.     pci->duplicate = dup;
  228.     pci->dx.nl = 1;
  229.     pci->dx.ff = NULLREC;
  230.     pci->level = 0;
  231.     CO(0) = -1;
  232.     CB(0) = 0L;
  233.     pci->root.brec = 0L;
  234.     pci->root.bend = 0;
  235.     pci->root.p0 = NULLREC;
  236.     write_if(pci->ixfile, 0L,(char *)&(pix->root),
  237.                (sizeof(BLOCK) + sizeof(IX_DISK)));
  238.     if (!cache_init)
  239.       {
  240.         init_cache();
  241.         cache_init = 1;
  242.       }
  243.     first_key(pix);
  244.     return ( IX_OK );
  245.   } /* make_index */
  246.  
  247.  
  248. /*  cache I/O for BPLUS  */
  249.  
  250. static void pascal 
  251. update_block()
  252.   {
  253.     if (block_ptr != &(pci->root))
  254.        BUFDIRTY(cache_ptr) = 1;
  255.   } /* update_block */
  256.  
  257.  
  258. static void pascal 
  259. init_cache()
  260.   {
  261.     register int  j;
  262.     for (j = 0; j < NUM_BUFS; j++)
  263.       {  BUFDIRTY(j) = 0;
  264.          BUFCOUNT(j) = 0;
  265.          BUFBLOCK(j).brec = NULLREC;
  266.       }
  267.   } /* init_cache */
  268.  
  269.  
  270. static int pascal 
  271. find_cache(r)
  272.   RECPOS r;
  273.   {
  274.     register int  j;
  275.     for (j = 0; j < NUM_BUFS; j++)
  276.       {
  277.         if((BUFBLOCK(j).brec == r) && (BUFHANDLE(j) == pci->ixfile))
  278.          {  cache_ptr = j;
  279.             return (1);
  280.       }  }
  281.     return (-1);
  282.   } /* find_cache */
  283.  
  284.  
  285. static int pascal 
  286. new_cache()
  287.   {
  288.     register int  i;
  289.     i = (cache_ptr + 1) % NU